package primary.code04_List;

import java.util.LinkedList;
import java.util.Stack;

/**
 * 反转链表
 * 思路：
 * 1. 当前节点：表示当前需要翻转指针的节点；
 * 2. 前节点：翻转后指向的节点；
 * 3. 后节点：翻转前，需要将当前节点的next保存；
 */
public class Code01_ReverseList {
    /**
     * 通过栈实现，空间复杂度 O(N)
     * <p>
     * 1. 遍历链表，将所有结点压入栈中
     * 2. 定义前节点 pre
     * 3. 弹出反转后的当前节点
     * 4. 修改前节点 next
     *
     * @param head
     * @return
     */
    private static Node reverseListByStack(Node head) {
        if (head == null || head.next == null) return head;
        LinkedList<Node> stack = new LinkedList();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        Node reverseHead = stack.pop();
        cur = reverseHead;
        while (stack.size() > 0) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        cur.next = null;
        return reverseHead;
    }

    private static Node reverseListByStack0(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node cur = head;
        Stack<Node> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        Node newHead = stack.pop();
        Node newTail = newHead;
        while (!stack.isEmpty()) {
            newTail.setNext(stack.pop());
            newTail = newTail.next;
        }
        newTail.setNext(null); // 将最后一个节点的next设置为null，否则将可能有环
        return newHead;
    }


    /**
     * 空间复杂度 O(1)
     * <p>
     * 使用 pre cur post 三个指针完成，
     * 分别用于找原前节点，当前操作节点，修改后保存原后节点
     *
     * @param head
     * @return
     */
    private static Node reverseListByPoint(Node head) {
        Node pre = null;
        Node cur = head;
        Node next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private static Node reverseListByPoint0(Node head) {
        Node cur = head;
        Node pre  = null;
        while (cur != null) {
            Node next = cur.next; // 记录下一节点，避免找不到
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 打印链表
     *
     * @param head
     * @return
     */
    private static String printList(Node head) {
        if (head == null) {
            return null;
        }
        StringBuilder sbResult = new StringBuilder();
        Node temp = head;
        while (temp != null) {
            sbResult.append(temp.data + "-->");
            temp = temp.next;
        }
        return sbResult.toString();
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;


        System.out.println("原链表：" + printList(node1));
        final Node reverseHead1 = reverseListByStack0(node1);
        System.out.println("栈，反转链表：" + printList(reverseHead1));

        System.out.println("原链表：" + printList(reverseHead1));
        final Node reverseHead2 = reverseListByPoint0(reverseHead1);
        System.out.println("指针，反转链表：" + printList(reverseHead2));
    }
}

